#ifndef LIST_H
#define LIST_H

#include "criticalsection.h"
#include "collection.h"

namespace Library
{

template<class O> class ListIterator;
template<class O> class ListEntry;

template<class O>
class List : public Collection<O>
{
	friend class ListIterator<O>;

	public:
						List(CriticalSection* cs=0);
		virtual			~List();

		// Collection overrides
		virtual bool8	add(O object);
		virtual bool8	addAll(Collection<O> * collection);
		virtual void	clear();
		virtual bool8	contains(O object);
		virtual bool8	containsAll(Collection<O> * collection);
		virtual bool8	remove(O object);
		virtual bool8	removeAll(Collection<O> * collection);
//		virtual bool8	retainAll(Collection<O> * collection);
		virtual bool8	isEmpty();
		virtual uint32	size();
		virtual void	vaporize();

		virtual Iterator<O> * iterator();

		// List originals
		virtual bool8	addIndex(uint32 index, O object);
		virtual	O		getIndex(uint32 index);
		virtual int32	indexOf(O object);
		virtual int32	lastIndexOf(O object);
		virtual bool8	removeIndex(uint32 index);
		virtual O 		setIndex(uint32 index, O object);

		// Iterators
		virtual ListIterator<O> * listIterator();
		virtual ListIterator<O> * listIterator(uint32 index);

	protected:
		uint32			age();
		ListEntry<O> *	entryAt(uint32 index);
		ListEntry<O> *	firstEntryOf(O object, uint32 * index = 0);
		ListEntry<O> *	lastEntryOf(O object, uint32 * index = 0);

		void			lock();
		void			unlock();

	protected:
		ListEntry<O> *	m_head;
		ListEntry<O> *	m_tail;
		uint32			m_size;
		uint32			m_age;
		bool8			m_threadsafe;
		CriticalSection*m_cs;

	// prohibited
	private:
		List(Collection<O> &);
		List & operator=(Collection<O> &);
};


/**
 * NOTICE: Upon instantiation, the ListIterator locks the List until it, the
 *         ListIterator, is deleted.  This means your ListIterator must be
 *         deleted *before* the List.
 */
template<class O>
class ListIterator : public Iterator<O>
{
	public:
						ListIterator(List<O> * list, uint32 index = 0);
		virtual			~ListIterator();

		// Iterator overrides
		virtual void	begin();
		virtual bool8	hasNext();
		virtual O		next();
		virtual bool8	remove();

		// ListIterator originals
		virtual bool8	add(O object);
		virtual void	end();
		virtual bool8	hasPrevious();
		virtual int32	nextIndex();
		virtual O		previous();
		virtual int32	previousIndex();
		virtual O		set(O object);

	protected:
				void	initialize();
				uint32	reindex();

	protected:
		List<O> *		m_list;
		ListEntry<O> *	m_cursor;
		ListEntry<O> *	m_last;
		uint32			m_index;
		uint32			m_age;

	// prohibited
	private:
		ListIterator();
		ListIterator(Iterator<O> &);
		ListIterator & operator=(Iterator<O> &);
};


template<class O>
class ListEntry
{
	friend class List<O>;
	friend class ListIterator<O>;

	public:
						ListEntry(O object);
						~ListEntry();

	public:
		O				m_object;
		ListEntry *		m_prev;
		ListEntry *		m_next;

	// prohibited
	private:
		ListEntry();
		ListEntry(ListEntry<O> &);
		ListEntry & operator=(ListEntry<O> &);
};



//============================================================================
// List
//============================================================================

//----------------------------------------------------------------------------
// Public
//
template<class O>
List<O>::List(CriticalSection* cs)
{
	m_head = 0;
	m_tail = 0;
	m_size = 0;
	m_age  = 0;
	m_cs   = cs;
}

template<class O>
List<O>::~List()
{
	clear();

	delete m_cs;
	m_cs = 0;
}

template<class O> void
List<O>::lock()
{
	if (m_cs)
		m_cs->Lock();
}


template<class O> void
List<O>::unlock()
{
	if (m_cs)
		m_cs->Unlock();
}

template<class O> bool8
List<O>::add(O object)
{
	ListEntry<O> * entry = new ListEntry<O>(object);

	lock();

	if (entry)
	{
		if (!m_head)
			m_head = m_tail = entry;
		else
		{
			entry->m_prev = m_tail;
			m_tail->m_next = entry;
			m_tail = entry;
		}

		m_size++;
		m_age++;
	}

	unlock();

	return (bool8)(entry != 0);
}

template<class O> bool8
List<O>::addIndex(uint32 index, O object)
{
	bool8 result = false;
	
	lock();

	ListEntry<O> *	entry;
	ListEntry<O> *	where;

	// Initial and tail additions are handled by add(O object).
	if (m_size && index < m_size)
	{
		entry = new ListEntry<O>(object);
		if (!entry)
		{
			result = false;
			goto end;
		}

		where = entryAt(index);

		// Add to the head of the list.
		if (index == 0)
		{
			entry->m_next = m_head;
			m_head->m_prev = entry;
			m_head = entry;
		}
		else
		{
			// Insert somewhere in the middle of the list.
			entry->m_prev = where->m_prev;
			entry->m_next = where;
			where->m_prev->m_next = entry;
			where->m_prev = entry;
		}

		m_size++;
		m_age++;

		result = true;
	}
	else
		result = add(object);

end:
	unlock();

	return result;
}

template<class O> bool8
List<O>::addAll(Collection<O> * collection)
{
	lock();

	Iterator<O> *	iterator = collection->iterator();
	uint32			size     = m_size;
	
	if (iterator)
	{
		while (iterator->hasNext())
			add(iterator->next());

		delete iterator;
	}

	bool8 result = (m_size == size + collection->size()); 

	unlock();

	return result;
}

template<class O> void
List<O>::clear()
{
	lock();

	while (m_head)
	{
		m_tail = m_head->m_next;
		delete m_head;
		m_head = m_tail;
	}

	m_head = 0;
	m_tail = 0;
	m_size = 0;
	m_age++;

	unlock();
}

template<class O> bool8
List<O>::contains(O object)
{
	return (bool8)(indexOf(object) != -1);
}

template<class O> bool8
List<O>::containsAll(Collection<O> * collection)
{
	bool8 success  = false;

	lock();

	Iterator<O> *	iterator = collection->iterator();

	if (iterator)
	{
		success = true;

		while (iterator->hasNext())
		{
			if (contains(iterator->next()) == false)
			{
				success = false;
				break;
			}
		}

		delete iterator;
	}

	unlock();

	return success;
}

template<class O> O
List<O>::getIndex(uint32 index)
{
	ListEntry<O> * entry = entryAt(index);

	if (entry)
		return entry->m_object;

	return 0;
}

template<class O> int32
List<O>::indexOf(O object)
{
	ListEntry<O> *	entry;
	uint32			i;

	entry = firstEntryOf(object, &i);
	if (entry)
		return i;

	return -1;
}

template<class O> bool8
List<O>::isEmpty()
{
	lock();

	bool8 result = (m_size == 0); 

	unlock();

	return result;
}

template<class O> Iterator<O> *
List<O>::iterator()
{
	return listIterator();
}

template<class O> int32
List<O>::lastIndexOf(O object)
{
	ListEntry<O> *	entry;
	uint32			i;

	entry = lastEntryOf(object, &i);
	if (entry)
		return i;

	return -1;
}

template<class O> ListIterator<O> *
List<O>::listIterator()
{
	return new ListIterator<O>(this);
}

template<class O> ListIterator<O> *
List<O>::listIterator(uint32 index)
{
	return new ListIterator<O>(this, index);
}

template<class O> bool8
List<O>::remove(O object)
{
	ListEntry<O> *	entry = firstEntryOf(object);

	if (!entry)
		return false;

	lock();

	if (entry->m_prev)
		entry->m_prev->m_next = entry->m_next;
	else
		m_head = entry->m_next;

	if (entry->m_next)
		entry->m_next->m_prev = entry->m_prev;
	else
		m_tail = entry->m_prev;

	delete entry;

	m_size--;
	m_age++;

	unlock();

	return true;
}

template<class O> bool8
List<O>::removeAll(Collection<O> * collection)
{
	Iterator<O> *	iterator = collection->iterator();
	bool8			success  = false;
	O				object;

	lock();

	if (iterator)
	{
		while (iterator->hasNext())
		{
			object = iterator->next();

			while (remove(object))
				/* do nothing */;
		}

		delete iterator;
	}

	unlock();

	return success;
}

template<class O> bool8
List<O>::removeIndex(uint32 index)
{
	ListEntry<O> *	entry = entryAt(index);

	if (!entry)
		return false;

	lock();

	if (entry->m_prev)
		entry->m_prev->m_next = entry->m_next;
	else
		m_head = entry->m_next;

	if (entry->m_next)
		entry->m_next->m_prev = entry->m_prev;
	else
		m_tail = entry->m_prev;

	delete entry;

	m_size--;
	m_age++;

	unlock();

	return true;
}

template<class O> O
List<O>::setIndex(uint32 index, O object)
{
	ListEntry<O> *	entry = entryAt(index);
	O				old = 0;

	lock();

	if (entry)
	{
		old = entry->m_object;
		entry->m_object = object;
	}

	unlock();

	return old;
}

template<class O> uint32
List<O>::size()
{
	lock();

	uint32 result = m_size;

	unlock();

	return result;
}

template<class O> void
List<O>::vaporize()
{
	ListEntry<O> *	item;

	lock();

	for (item = m_head; item; item = item->m_next)
	{
		delete item->m_object;
		item->m_object = 0;
	}

	// Yes we walk the list twice, but it's better than duplicating code.
	clear();

	unlock();
}

//----------------------------------------------------------------------------
// Protected
//
template<class O> uint32
List<O>::age()
{
	lock();

	uint32 age = m_age;

	unlock();

	return age;
}

template<class O> ListEntry<O> *
List<O>::entryAt(uint32 index)
{
	ListEntry<O> *	entry = 0;
	uint32			i;

	lock();

	if (!m_head || index >= m_size)
		goto unlock;

	if (index < m_size / 2)
	{
		entry = m_head;

		for (i = 0; i != index; i++)
			entry = entry->m_next;
	}
	else
	{
		entry = m_tail;

		for (i = m_size - 1; i != index; i--)
			entry = entry->m_prev;
	}

unlock:

	unlock();

	return entry;
}

template<class O> ListEntry<O> *
List<O>::firstEntryOf(O object, uint32 * index)
{
	lock();

	ListEntry<O> *	entry = m_head;
	uint32			i;

	for (i = 0; entry; i++, entry = entry->m_next)
	{
		if (entry->m_object == object)
			break;
	}

	if (index)
		*index = i;

	unlock();

	return entry;
}

template<class O> ListEntry<O> *
List<O>::lastEntryOf(O object, uint32 * index)
{
	lock();

	ListEntry<O> *	entry = m_tail;
	uint32			i;

	for (i = m_size - 1; entry; i--, entry = entry->m_prev)
	{
		if (entry->m_object == object)
			break;
	}

	if (index)
		*index = i;

	unlock();

	return entry;
}



//============================================================================
// ListIterator
//============================================================================

//----------------------------------------------------------------------------
// Public
//
template<class O>
ListIterator<O>::ListIterator(List<O> * alist, uint32 index)
{
	alist->lock();

	m_list		= alist;
	m_cursor	= alist->entryAt(index);
	m_last		= 0;
	m_index		= index;
	m_age		= alist->age();
}

template<class O>
ListIterator<O>::~ListIterator()
{
	m_list->unlock();
}

template<class O> bool8
ListIterator<O>::add(O object)
{
	// Additions invalidate m_last.
	m_last = 0;

	return (m_list->addIndex(reindex(), object));
}

template<class O> void
ListIterator<O>::begin()
{
	m_cursor	= m_list->entryAt(0);
	m_last		= 0;
	m_index		= 0;
	m_age		= m_list->age();
}

template<class O> void
ListIterator<O>::end()
{
	m_cursor	= m_list->entryAt(m_list->m_size);
	m_last		= 0;
	m_index		= m_list->size();
	m_age		= m_list->age();
}

template<class O> bool8
ListIterator<O>::hasNext()
{
	// Update the pointers if necessary.
	reindex();

	return (bool8)(m_cursor != 0);
}

template<class O> bool8
ListIterator<O>::hasPrevious()
{
	// Update the pointers if necessary.
	reindex();

	if (m_cursor)
		return (bool8)(m_cursor->m_prev != 0);

	return (bool8)(m_list->m_tail != 0);
}

template<class O> O
ListIterator<O>::next()
{
	O object = 0;

	// Update the pointers if necessary.
	reindex();

	if (m_cursor)
	{
		m_last = m_cursor;
		object = m_last->m_object;
		m_cursor = m_cursor->m_next;

		m_index++;
	}

	return object;
}

template<class O> int32
ListIterator<O>::nextIndex()
{
	return reindex();
}

template<class O> O
ListIterator<O>::previous()
{
	O object = 0;

	// Update the pointers if necessary.
	reindex();

	// Invalidate until we actually move!
	m_last = 0;

	if (m_cursor)
	{
		// Adjust as long as we are not at the head...
		if (m_cursor->m_prev)
		{
			m_last = m_cursor->m_prev;
			m_cursor = m_last;
		}
	}
	else
	{
		// We are at the tail of the list...
		m_cursor = m_list->m_tail;
		m_last = m_cursor;
	}

	// If valid, update.
	if (m_last)
	{
		object = m_last->m_object;
		m_index--;
	}

	return object;
}

template<class O> int32
ListIterator<O>::previousIndex()
{
	return reindex() - 1;
}

template<class O> bool8
ListIterator<O>::remove()
{
	ListEntry<O> *	last;
	uint32			lastIndex;

	// Update the pointers if necessary.
	reindex();

	if (m_last)
	{
		last		= m_last;
		lastIndex	= 0;

		// Where is last anyway?
		while (last)
		{
			last = last->m_prev;
			lastIndex++;
		}

		// Shift our count if we are about to loose one in front of us.
		if (--lastIndex < m_index)
			m_index--;
		
		return m_list->removeIndex(lastIndex);
	}

	return false;
}

template<class O> O
ListIterator<O>::set(O object)
{
	O old = 0;

	if (m_last)
	{
		old = m_last->m_object;
		m_last->m_object = object;
	}

	return old;
}

//----------------------------------------------------------------------------
// Protected
//
template<class O> uint32
ListIterator<O>::reindex()
{
	ListEntry<O> *	entry;

	if (m_age == m_list->m_age)
		return m_index;

	// Update our age reference.
	m_age = m_list->m_age;

	// Are we at the beginning of an uninitialized list?  Or maybe we just
	// think we are at the end of an initialized list.  It doesn't matter,
	// requery just to make sure...
	if (m_cursor == 0)
	{
		m_cursor = m_list->entryAt(m_index);
	}
	// Otherwise, we're not sure where we are...
	else
	{
		entry = m_cursor;
		m_index	= 0;

		while (entry)
		{
			entry = entry->m_prev;
			m_index++;
		}
	}

	return m_index;
}

//============================================================================
// ListEntry
//============================================================================

//----------------------------------------------------------------------------
// Protected
//
template<class O>
ListEntry<O>::ListEntry(O object)
{
	m_object	= object;
	m_prev		= 0;
	m_next		= 0;
}

template<class O>
ListEntry<O>::~ListEntry()
{
}

}; // namespace Library

#endif
